#ifndef LFU_CACHE_HPP
#define LFU_CACHE_HPP

#include <mutex>
#include <unordered_map>

#include "../CachePolicyIface.h"
#include "./LfuList.hpp"

namespace CachePool
{
    template <typename Key, typename Value>
    class LfuCache : public CachePolicyIface<Key, Value>
    {
    public:
        using Node = typename LfuList<Key, Value>::Node;
        using NodePtr = std::shared_ptr<Node>;
        using NodeMap = std::unordered_map<Key, NodePtr>;

        LfuCache(const size_t capacity, const size_t maxAverageFreq = 10)
            : capacity_(capacity),
              minFreq_(0), // 只要有节点，约定最小频率总是1
              maxAverageFreq_(maxAverageFreq),
              curAverageFreq_(0),
              curTotalFreq_(0)
        {
        }

        ~LfuCache() override = default;

        void set(const Key &key, const Value &value) override
        {
            if (this->capacity_ <= 0)
            {
                return;
            }

            std::lock_guard<std::mutex> lock(this->mutex_);

            // 未找到插入，找到更新
            auto it = this->nodeMap_.find(key);
            if (it == this->nodeMap_.end())
            {
                this->addNode(key, value);
                return;
            }

            // 重置其value值
            it->second->value_ = value;
            // 找到了直接调整就好了，不用再去get中再找一遍，但其实影响不大
            // OPTIMIAZE: get()才会value赋值，这里为了不修改const Value &value形参，传it->second->value_而不是value
            this->modNode(it->second, it->second->value_); // get需要获取value
        }

        // value值为传出参数
        bool get(const Key &key, Value &value) override
        {
            std::lock_guard<std::mutex> lock(this->mutex_);

            auto it = this->nodeMap_.find(key);
            if (it == this->nodeMap_.end())
            {
                return false;
            }

            this->modNode(it->second, value);
            return true;
        }

        Value get(const Key &key) override
        {
            Value value{};
            this->get(key, value);
            return value;
        }

        // 清空缓存,回收资源
        void purge()
        {
            this->freqToFreqList_.clear();
            this->nodeMap_.clear();
        }

    private:
        void addNode(const Key &key, const Value &value); // 添加缓存
        void evictLfuNode();                              // 移除缓存中的过期数据
        void delListNode(NodePtr node);                   // 从频率列表中移除节点
        void delFreq(const size_t nodeFreq);              // 减少总频率和平均频率
        void addListNode(NodePtr node);                   // 添加到频率列表
        void addFreq();                                   // 增加总频率和平均频率
        void handleOverMaxAverageFreq();                  // 处理当前平均访问频率超过上限的情况
        void modMinFreq();                                // 更新最小频率
        void modNode(NodePtr node, Value &value);         // 获取缓存并修改频率

        size_t capacity_;       // 缓存容量
        size_t minFreq_;        // 最小访问频次（用于找到最小访问频次结点）
        size_t maxAverageFreq_; // 最大平均访问频次
        size_t curAverageFreq_; // 当前平均访问频次
        size_t curTotalFreq_;   // 当前访问所有缓存次数总数

        std::mutex mutex_; // 互斥锁
        // std::unordered_map<size_t, LfuList<Key, Value> *> freqToFreqList_; // 访问频次到该频次链表的映射
        // OPTIMIZE: * -> std::unique_ptr<>
        std::unordered_map<size_t, std::unique_ptr<LfuList<Key, Value>>> freqToFreqList_; // 访问频次到该频次链表的映射
        NodeMap nodeMap_;                                                                 // key 到 缓存节点的映射
    };

    template <typename Key, typename Value>
    void LfuCache<Key, Value>::addNode(const Key &key, const Value &value)
    {
        // 如果不在缓存中，则需要判断缓存是否已满
        if (this->nodeMap_.size() == this->capacity_)
        {
            // 缓存已满，删除最不常访问的结点，更新当前总访问频次和平均访问频次
            this->evictLfuNode();
        }

        // 创建新结点，将新结点添加进入，更新最小访问频次
        NodePtr node = std::make_shared<Node>(key, value);
        this->addListNode(node);
        this->nodeMap_[key] = node;
        this->addFreq();

        // minFreq_ = std::min(minFreq_, 1);
        // OPTIMIZE: 只要有节点，约定最小频率总是1
        this->minFreq_ = 1; // 只要有节点，约定最小频率总是1
    }

    template <typename Key, typename Value>
    void LfuCache<Key, Value>::evictLfuNode()
    {
        NodePtr node = this->freqToFreqList_[this->minFreq_]->getFirstNode(); // 最低频率链表获取第一个节点
        this->delListNode(node);
        this->nodeMap_.erase(node->key_);
        delFreq(node->freq_); // 这是最小频率，因为这个节点没了，访问频率自然降低
    }

    template <typename Key, typename Value>
    void LfuCache<Key, Value>::delListNode(NodePtr node)
    {
        // 检查结点是否为空
        if (!node)
        {
            return;
        }

        // 这是通用的删除方法，不一定是获取this->minFreq_删除，所以每次再取一次freq
        // 如handleOverMaxAverageFreq()调整各节点频率时会用
        size_t freq = node->freq_;
        this->freqToFreqList_[freq]->delNode(node); // 链表里封装的删除节点操作
    }

    template <typename Key, typename Value>
    void LfuCache<Key, Value>::delFreq(const size_t nodeFreq)
    {
        // 减少总访问频次和平均访问频次
        this->curTotalFreq_ -= nodeFreq;

        if (this->nodeMap_.empty())
        {
            this->curAverageFreq_ = 0;
        }
        else
        {
            this->curAverageFreq_ = this->curTotalFreq_ / this->nodeMap_.size(); // 哈希表大小即节点数量
        }
    }

    template <typename Key, typename Value>
    void LfuCache<Key, Value>::addListNode(NodePtr node)
    {
        // 检查结点是否为空
        if (!node)
        {
            return;
        }

        // 添加进入相应的频次链表前需要判断该频次链表是否存在
        size_t freq = node->freq_;
        if (this->freqToFreqList_.find(freq) == this->freqToFreqList_.end())
        {
            this->freqToFreqList_[freq] = std::make_unique<LfuList<Key, Value>>(freq); // 不存在则创建
        }

        this->freqToFreqList_[freq]->addNode(node); // 是否存在都加入节点，调用链表封装方法
    }

    template <typename Key, typename Value>
    void LfuCache<Key, Value>::addFreq()
    {
        ++this->curTotalFreq_;

        if (this->nodeMap_.empty())
        {
            this->curAverageFreq_ = 0;
        }
        else
        {
            this->curAverageFreq_ = this->curTotalFreq_ / this->nodeMap_.size();
        }

        if (this->curAverageFreq_ > this->maxAverageFreq_)
        {
            this->handleOverMaxAverageFreq();
        }
    }

    template <typename Key, typename Value>
    void LfuCache<Key, Value>::handleOverMaxAverageFreq()
    {
        if (this->nodeMap_.empty())
        {
            return;
        }

        // 当前平均访问频次已经超过了最大平均访问频次，所有结点的访问频次- (最大平均频率 / 2)
        for (auto it = this->nodeMap_.begin(); it != this->nodeMap_.end(); ++it)
        {
            // 检查结点是否为空
            if (!it->second)
            {
                continue;
            }

            NodePtr node = it->second;

            // 先从当前频率列表中移除
            this->delListNode(node);

            // 减少频率
            // node->freq -= this->maxAverageNum_ / 2;
            // if (node->freq < 1)
            //     node->freq = 1;
            // OPTIMIZE: 细化减少频率操作，避免size_t溢出；要更新总频率
            if (node->freq_ <= this->maxAverageFreq_ / 2) // 节点频率最小为1
            {
                node->freq_ = 1;

                this->curTotalFreq_ = this->curTotalFreq_ - node->freq_ + 1; // 注意要更新总频率
            }
            else
            {
                node->freq_ -= this->maxAverageFreq_ / 2;

                this->curTotalFreq_ -= this->maxAverageFreq_ / 2;
            }

            // 添加到新的频率列表
            this->addListNode(node);
        }

        // 更新平均频率
        this->curAverageFreq_ = this->curTotalFreq_ / this->nodeMap_.size();

        // 更新最小频率，相比上面每个节点算最小，对每频率链表算最小性能更好
        this->modMinFreq();
    }

    template <typename Key, typename Value>
    void LfuCache<Key, Value>::modMinFreq()
    {
        this->minFreq_ = INT8_MAX;
        for (const auto &pair : this->freqToFreqList_)
        {
            if (pair.second && !pair.second->isEmpty()) // 有链表且链表不为空，因为modNode()移动节点不删链表会存在空链表
            {
                this->minFreq_ = std::min(this->minFreq_, pair.first);
            }
        }

        if (minFreq_ == INT8_MAX)
        {
            this->minFreq_ = 1; // 只要有节点，约定最小频率总是1
        }
    }

    template <typename Key, typename Value>
    void LfuCache<Key, Value>::modNode(NodePtr node, Value &value)
    {
        // 找到之后需要将其从低访问频次的链表中删除，并且添加到+1的访问频次链表中
        value = node->value_; // 把value值返回，get()会用到该方法

        // 从原有访问频次的链表中删除节点，+1，加入新链表
        this->delListNode(node);
        ++node->freq_;
        this->addListNode(node);

        // 如果当前node的访问频次如果等于minFreq+1，并且其前驱链表为空，则说明
        // freqToFreqList_[node->freq - 1]链表因node的迁移已经空了
        // 需要删除旧链表也可以不删因为很快总会有更小的不需要频繁删增链表，更新最小访问频次
        if (node->freq_ - 1 == this->minFreq_ && this->freqToFreqList_[node->freq_ - 1]->isEmpty())
        {
            // this->freqToFreqList_.erase(node->freq - 1);
            ++this->minFreq_;
        }

        // 总访问频次和当前平均访问频次都随之增加
        this->addFreq();
    }
} // namespace CachePool

#endif // LFU_CACHE_HPP